package linkedtable;

import org.junit.Test;

/**
 * @Description 61. 旋转链表
 * @Author Firenut
 * @Date 2023-01-15 22:27
 */
public class T61_rotateRight {

    /*
    测试用例:
    [1] 0
    [1] 99
    [1,2] 0
    [1,2] 2
    [0,1,2] 4
    * */
    @Test
    public void test() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = null;
        ListNode node = rotateRight(node1, 2);
        System.out.println(node.val);

    }

    /*
        当向右移动的次数 k (k≥n) 时，我们仅需要向右移动 k%n 次即可
    * */

    // 法1: 多指针解法
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null||k==0){
            return head;
        }

        ListNode p = head, p1;
        int len = 1;
        while (p.next != null) { //计算链表的长度
            p = p.next;
            len++;
        }

        k %= len;   //取模
        if(k==0){
            return head;
        }

        p1 = head;
        for (int i = 1; i < len - k; i++) {
            p1 = p1.next;
        }

        ListNode p2 = p1.next;
        p1.next = null;
        p.next = head;
        return p2;
    }

    // 法2: 链表先成环,再从指定位置断开(其实和法1差不多,法1是先断开后连接)
    // 测试案例: [1] 1
    public ListNode rotateRight2(ListNode head, int k) {
        if(head==null||k==0){
            return head;
        }

        ListNode p = head, p1;
        int len = 1;
        while (p.next != null) { //计算链表的长度
            p = p.next;
            len++;
        }
//        p.next = head;  //连接成环

        k %= len;       //取模
        if(k==0){
            return head;
        }

        p.next = head;  //连接成环要放后面，如果前面k取模为0,那么会导致变成循环链表了

        p1 = head;
        for (int i = 1; i < len - k; i++) {
            p1 = p1.next;
        }

        ListNode p2 = p1.next;
        p1.next = null;
        return p2;
    }
}
